﻿//给定一个经过编码的字符串，返回它解码后的字符串。
//编码规则为 : k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
//
//输入：s = "3[a]2[bc]"
//输出："aaabcbc"
//
//输入：s = "3[a2[c]]"
//输出："accaccacc"
//
//输入：s = "2[abc]3[cd]ef"
//输出："abcabccdcdcdef"
//
//输入：s = "abc3[cd]xyz"
//输出："abccdcdcdxyz"
//
//提示：
//	1 <= s.length <= 30
//	s 由小写英文字母、数字和方括号 '[]' 组成
//	s 保证是一个 有效 的输入。
//	s 中所有整数的取值范围为[1, 300]

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> st;
        st.push("");
        int i = 0, n = s.size();
        while (i < n) {
            if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }
            else if (s[i] == '[') {
                i++; // 把括号后⾯的字符串提取出来

                string tmp = "";
                while (s[i] >= 'a' && s[i] <= 'z') {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp);
            }
            else if (s[i] == ']') {
                string tmp = st.top();
                st.pop();
                int k = nums.top();
                nums.pop();
                while (k--) {
                    st.top() += tmp;
                }
                i++; // 跳过这个右括号

            }
            else {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp += s[i];
                    i++;
                }
                st.top() += tmp;
            }
        }
        return st.top();
    }
};